/*
 * @lc app=leetcode.cn id=435 lang=javascript
 *
 * [435] 无重叠区间
 */

// @lc code=start
/**
 * @param {number[][]} intervals
 * @return {number}
 */

// 可转换为最长上升子序列问题
// 移除最小数量的区间 剩下的区间就是一个递增的序列了 找到这个最长的递增序列就相当于找到需要移除的最小数量的区间
// 从终点的动态规划
var eraseOverlapIntervals1 = function(intervals) {
    if (intervals.length == 0) return 0
    intervals.sort((a, b) => a[1]-b[1])
    let dp = new Array(intervals.length).fill(0)
    dp[0] = 1
    let max = 1
    for (let i = 1; i < intervals.length; i++) {
        let j = i
        while (j > 0) {
            if (intervals[--j][1] <= intervals[i][0])
                dp[i] = Math.max(dp[i], dp[j])
        }
        dp[i] += 1
        max = Math.max(max, dp[i])
    }
    console.log(intervals.length - max)
    return intervals.length - max
};

// 从起点的动态规划
var eraseOverlapIntervals2 = function(intervals) {
    if (intervals.length == 0) return 0
    intervals.sort((a, b) => a[0]-b[0])
    let dp = new Array(intervals.length).fill(0)
    dp[0] = 1
    let max = 1
    for (let i = 1; i < intervals.length; i++) {
        let j = i
        while (j > 0) {
            if (intervals[--j][1] <= intervals[i][0])
                dp[i] = Math.max(dp[i], dp[j])
        }
        dp[i] += 1
        max = Math.max(max, dp[i])
    }
    return intervals.length - max
}

// 贪心算法
// 按起点排序, 从头到后遍历, 碰到有重合的区间尽量选择终点靠前的区间, 删除靠后的区间
var eraseOverlapIntervals3 = function(intervals) {
    if (intervals.length == 0) return 0
    intervals.sort((a, b) => a[0]-b[0])
    let pre = 0, count = 0
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= intervals[pre][1]) {
            pre = i
        } else {
            if (intervals[i][1] < intervals[pre][1]) {
                pre = i
            }
            count++
        }
    }
    return count
}

// 贪心算法
// 按终点排序, 从头到后遍历, 选择后面区间选择起点 > 前面终点的区间
var eraseOverlapIntervals4 = function(intervals) {
    if (intervals.length == 0) return 0
    intervals.sort((a, b) => a[1]-b[1])
    let pre = 0, count = 0
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= intervals[pre][1]) {
            pre = i
            count++
        }
    }
    return intervals.length - count
}

// @lc code=end

let arr = [[1,100],[11,22],[1,11],[2,12]]

eraseOverlapIntervals2(arr)
